Fyodor Tolbukhin sinh năm 1894 trong một gia đình nông dân tại tỉnh Yaroslavl phía Tây Bắc Moskva. Ông tình nguyện nhập ngũ năm 1914 và chiến đấu trong quân đội Đế quốc Nga trong Chiến tranh thế giới thứ nhất. Tại đây Tolbukhin liên tục được thăng cấp từ binh nhì lên đại úy năm 1916, ông cũng được khen thưởng vài lần vì thành tích chiến đấu dũng cảm.

Tháng 8 năm 1918 Tolbukhin gia nhập Hồng quân, ông được giao vị trí Tham mưu trưởng của Sư đoàn bộ binh số 56. Sau khi Nội chiến Nga kết thúc năm 1921, Tolbukhin tiếp tục phục vụ trong các đơn vị tham mưu và vào học tại Học viện quân sự Frunze cho đến năm 1931. Năm 1937 ông được thăng chức chỉ huy sư đoàn và năm 1938 là Tham mưu trưởng Quân khu Zacapcazơ.

Tolbukhin giữ vị trí này cho đến khi Chiến tranh giữ nước vĩ đại nổ ra, tháng 8 năm 1941, ông trở thành Tham mưu trưởng Phương diện quân Crimea. Từ tháng 5 đến tháng 7 năm 1942 ông là Phó tư lệnh Quân khu Stalingrad, sau đó là Tư lệnh Tập đoàn quân số 57 đến tháng 3 năm 1943. Tập đoàn quân của Tolbukhin đã tham chiến trong Trận Stalingrad dưới sự chỉ huy chung của Thượng tướng Andrey Yeryomenko, người đã đánh giá rất cao khả năng tổ chức và kỹ năng quân sự của Tolbukhin. Sau chiến thắng của Hồng quân ở Stalingrad, ông được thăng chức Tư lệnh Phương diện quân Nam.

Tháng 10 năm 1943 Phương diện quân Nam được đổi tên thành Phương diện quân Ukraina 4, Tolbukhin đã lãnh đạo phương diện quân này cùng với Phương diện quân Ukraina 3 của tướng Rodion Malinovsky giải phóng phần lớn lãnh thổ Ukraina khỏi sự chiếm đóng của quân đội Đức Quốc xã. Từ tháng 5 năm 1944, Tolbukhin được chuyển sang làm Tư lệnh Phương diện quân Ukraina 3 tham gia đánh đuổi quân Đức khỏi các nước vùng Balkan và Rumani từ tháng 6 đến tháng 10 năm 1944. Ngày 12 tháng 9 năm 1944, 2 ngày sau khi người đồng đội Malinovsky được phong Nguyên soái, Tolbukhin cũng được thăng cấp Nguyên soái Liên bang Xô viết. Trong khi phương diện quân của Malinovsky tiến về hướng Tây Bắc qua Hungary và Nam Tư, đội quân của Tolbukhin tiến về phía Nam và tham gia đẩy quân Đức ra khỏi phần lớn lãnh thổ Bulgari. Trong chiến dịch mùa Đông, ông đã lãnh đạo Hồng quân tiến về phía Tây Bắc, đuổi người Đức khỏi lãnh thổ Nam Tư và sau đó tiến vào Nam Hungary.

Sau chiến tranh, Tolbukhin giữ chức Tổng tư lệnh các lực lượng vũ trang phía Nam bao gồm cả khu vực Balkan. Tháng 1 năm 1947 ông chuyển về làm Tư lệnh Quân khu Zacapcazơ đến khi mất ngày 17 tháng 10 năm 1949.